package likou

// 401 号算法题

import (
	"fmt"
	"math/bits"
)

// 开头大写，表示该方法为 public
// 解法1： 暴力解法，双重 for 循环
func ReadBinaryWatch(turnedOn int) (ans []string) {
	for h := uint8(0); h < 12; h++ {
		for m := uint8(0); m < 60; m++ {
			// 计算对应二进制位上的1的个数， 1的个数相加等于 turnedOn 的，就 加入结果集中
			if bits.OnesCount8(h)+bits.OnesCount8(m) == turnedOn {
				ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
			}
		}
	}
	return
}




// 方法2： 同样的枚举，利用组合的思路

// dfs 在数组内，求指定长度的全排列
func dfs(nums []byte, count, sum, idx int, rst *[]byte) {
	if count == 0 {
		*rst = append(*rst, byte(sum))
		return
	}

	for i := idx; i < len(nums); i++ {
		//fmt.Println(nums[i])
		dfs(nums, count - 1, sum + int(nums[i]), i + 1, rst)
	}
}

// 封装 dfs，返回 对应的结果
func findCombinations(nums []byte, count int) (rst []byte) {
	dfs(nums, count, 0, 0, &rst)   // 注意dfs， 传递指针进去， 因为 有 append操作，将返回新的对象
	return
}

// 双重循环 加上 dfs去做
func ReadBinaryWatch1(turnedOn int) []string {
	// 定义表示 小时和分钟的数组
	nums1 := []byte {8, 4, 2, 1}
	nums2 := []byte {32, 16, 8, 4, 2, 1}
	// 定义结果集
	var rst []string

	for i := 0; i <= turnedOn; i++ {
		// 获取时间
		hours := findCombinations(nums1, i)
		// 获取分钟
		minutes := findCombinations(nums2, turnedOn - i)
		// 进行组合
		for _, hour := range hours {
			if hour > 11 {continue}
			for _, minute := range minutes {
				if minute > 59 {continue}
				// 拼接结果并加入到结果集
				rst = append(rst, fmt.Sprintf("%d:%02d", hour, minute))
			}
		}
	}

	return rst
}




// 上面写法的优化 ： 老师码云上的写法， 去除了使用指针了。 改为定义闭包，我觉得写的更合适。
/*
func readBinaryWatch(turnedOn int) []string {
	var nums1 = []int{8, 4, 2, 1}
	var nums2 = []int{32, 16, 8, 4, 2, 1}
	var res = make([]string, 0)

	// bug 修复：需要等于，不然会少一种组合，总共是[0，turnedOn]种
	for i := 0; i <= turnedOn; i++ {
		// 拿到 i 个小时的组合
		var hours = findCombinations(nums1, i)
		// 拿到 turnedOn - i 个分钟的组合
		var minutes = findCombinations(nums2, turnedOn - i)
		for _, hour := range hours {
			if hour > 11 {
				continue
			}
			for _, minute := range minutes {
				if minute > 59 {
					continue
				}
				var minuteStr = strconv.Itoa(minute)
				if minute < 10 {
					minuteStr = "0" + strconv.Itoa(minute)
				}
				res = append(res, strconv.Itoa(hour) + ":" + minuteStr)
			}
		}
	}

	return res
}

func findCombinations(nums []int, count int) []int {
	var res = make([]int, 0)

	var dfs func(int, int, int)
	dfs = func(count int, sum int, start int) {
		if count == 0 {
			res = append(res, sum)
			return
		}

		for i := start; i < len(nums); i++ {
			dfs(count - 1, sum + nums[i], i + 1)
		}
	}

	dfs(count, 0, 0)
	return res
}
*/
